//
//  UnionFind.hpp
//  DataStructureC++
//
//  Created by zhangbaochuan on 2020/4/20.
//  Copyright © 2020 Geex. All rights reserved.
//

#ifndef UnionFind_hpp
#define UnionFind_hpp

#include <stdio.h>
#include <assert.h>
#include <ctime>
#include <iostream>
#include <iomanip>

namespace UF {
class UnionFind {
private:
    int *id;
    int count;
    
public:
    UnionFind (int n) {
        count = n;
        id = new int(n);
        for (int i = 0; i< n; i++) {
            id[i] = i;
        }
    }
    
    ~UnionFind () {
//        delete [] id;
    }
    
    int find(int p) {
        assert(p >= 0 && p < count);
        return id[p];
    }
    
    bool isConnection(int p, int q) {
        return find(p) == find(q);
    }
    
    void unions(int p, int q) {
        int pID = find(p);
        int qID = find(q);
        
        for (int i = 0; i < count; i++) {
            if (id[i] == pID) {
                id[i] = qID;
            }
        }
    }
};
}

#pragma mark -- UnionFind Quick
namespace UFQuick {
class UnionFind {
private:
    int *parent;
    int count;
    
public:
    UnionFind(int n) {
        count = n;
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
    
    ~UnionFind() {
        delete [] parent;
    }
    
    int find(int p) {
        assert(p >= 0 && p < count);
        while (p != parent[p]) {
            p = parent[p];
        }
        return p;
    }
    
    bool isConnection(int p, int q) {
        int pValue = find(p);
        int qValue = find(q);
        return pValue == qValue;
    }
    
    void unions(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) {
            return;
        }else {
            parent[pRoot] = qRoot;
        }
    }
};

}

#pragma mark -- UnionFind Size
namespace UFSize {
class UnionFind {
private:
    int *parent;
    int *sz;// 以i为根h包含的节点数
    int count;
    
public:
    UnionFind(int n) {
        count = n;
        parent = new int[n];
        sz = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            sz[i] = 1;
        }
    }
    
    ~UnionFind() {
        delete [] parent;
        delete [] sz;
    }
    
    int find(int p) {
        assert(p >= 0 && p < count);
        while (p != parent[p]) {
            p = parent[p];
        }
        return p;
    }
    
    bool isConnection(int p, int q) {
        return find(p) == find(q);
    }
    void unions(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) { return; }
        
        if (sz[pRoot] < sz[qRoot]) {
            parent[pRoot] = qRoot;
            sz[qRoot] += sz[pRoot];
        } else {
            parent[qRoot] = pRoot;
            sz[pRoot] += sz[qRoot];
        }
    }
    
};

}

#pragma mark - UnionFind Path Compression
namespace UFPath {
class UnionFind {
private:
    int *parent;
    int *rank;
    int count;
public:
    UnionFind(int n) {
        count = n;
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }
    ~UnionFind() {
        delete [] parent;
        delete [] rank;
    }
    
    int find(int p) {
        assert(p >=0 && p < count);
        while (p != parent[p]) {
            parent[p] = parent[parent[p]];
            p = parent[p];
        }
        return p;
//        if (p != parent[p]) {
//            parent[p] = find(parent[p]);
//        }
        return parent[p];
    }
    
    bool isConnection(int p, int q) {
        return find(p) == find(q);
    }
    void unions(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) { return; }
        
        if (rank[pRoot] < rank[qRoot]) {
            parent[pRoot] = qRoot;
        } else if (rank[pRoot] > rank[qRoot]) {
            parent[qRoot] = pRoot;
        } else {
            parent[pRoot] = qRoot;
            rank[qRoot] += 1;
        }
    }
};
}

#pragma mark -- Test Helper

namespace UnionFindTestHelper {
    inline void testUF(int n) {
        srand((unsigned int)time(NULL));
        UF::UnionFind uf = UF::UnionFind(n);
        time_t start = clock();
        
//        for (int i = 0; i < n; i++) {
            int a = rand() % n;
            int b = rand() % n;
            uf.unions(a, b);
//        }
        
//        for (int i = 0; i < n; i++) {
//            int a = rand() % n;
//            int b = rand() % n;
       int iscon = uf.isConnection(a, b);
//        }
        
        time_t end = clock();
        
        double t = (double)(end - start)/CLOCKS_PER_SEC;
        std::cout<<"UF:"<< 2*n <<" ops "<< std::setiosflags(std::ios::fixed) <<std::setprecision(10) <<t <<std::endl;
        uf.~UnionFind();
    }

inline void testUFQuick(int n) {
    UFQuick::UnionFind uf = UFQuick::UnionFind(n);
    
    int a = 2;
    int b = 3;
    uf.unions(a, b);
    uf.find(2);
    int iscon = uf.isConnection(a, b);
    
}

inline void testUFSize(int n) {
//    srand((unsigned int)time(NULL));
    UFSize::UnionFind uf = UFSize::UnionFind(n);
//    time_t start = clock();
    
//    for (int i = 0; i < n; i++) {
        int a = rand() % n;
        int b = rand() % n;
        uf.unions(a, b);
//    }
    
//    for (int i = 0; i < n; i++) {
//        int a = rand() % n;
//        int b = rand() % n;
      int iscol = uf.isConnection(a, b);
//    }
    
//    time_t end = clock();
//
//    double t = (double)(end - start)/CLOCKS_PER_SEC;
//    std::cout<<"UFSize:"<< 2*n <<" ops "<< std::setiosflags(std::ios::fixed) <<std::setprecision(10) <<t <<std::endl;
}

inline void testUFPath(int n) {
       srand((unsigned int)time(NULL));
       UFPath::UnionFind uf = UFPath::UnionFind(n);
       time_t start = clock();
       
       for (int i = 0; i < n; i++) {
           int a = rand() % n;
           int b = rand() % n;
           uf.unions(a, b);
       }
       
       for (int i = 0; i < n; i++) {
           int a = rand() % n;
           int b = rand() % n;
           uf.isConnection(a, b);
       }
       
       time_t end = clock();
       
       double t = (double)(end - start)/CLOCKS_PER_SEC;
       std::cout<<"UFPath:"<< 2*n <<" ops "<< std::setiosflags(std::ios::fixed) <<std::setprecision(10) <<t <<std::endl;
   }
    
inline void test() {
    int n = 10;
    testUF(n);
    testUFQuick(n);
    testUFSize(n);
    testUFPath(n);
}
}

#endif /* UnionFind_hpp */
